6.5 Sets of parallel segments (segment_set)

segment_set I

1. Definition

An instance S of the parameterized data type is a collection of items (seg$\_item$). Every item in S contains as key a line segment with a fixed direction α (see data type segment) and an information from data type I, called the information type of S. α is called the orientation of S. We use < s, i > to denote the item with segment s and information i. For each segment s there is at most one item < s, i > ∈S.


2. Creation

a) S (double &alpha#alpha;)

b) S

creates an empty instance of type with orientation α. Variant b) creates a segment set of orientation zero, i.e., for horizontal segments.


3. Operations

& truecm & truecm & segment key seg_item it returns the segment of item it. it is an item in .

I inf seg_item it returns the information of item it. it is an item in .

seg_item insert segment s, I i associates the information i with segment s. If there is an item < s, j > in then j is replaced by i, else a new item < s, i > is added to S. In both cases the item is returned.

ps_item lookup segment s returns the item with segment s (nil if no such item exists in ).

listseg_item intersection segment q returns all items < s, i >  ∈ S with s∩q≠∅. q is orthogonal to the segments in .

listseg_item intersection line l returns all items < s, i >  ∈ S with s∩l≠∅. l is orthogonal to the segments in .

void del segment s deletes the item with segment s from .

void del_item seg_item it removes item it from . it is an item in .

void change_inf seg_item it, I i makes i the information of item it. it is an item in .

void clear makes the empty segment_set.

bool empty returns true iff is empty.

int size returns the size of .


4. Implementation

Segment sets are implemented by dynamic segment trees based on BB[α] trees ([Wi85, Lu78]) trees. Operations key, inf, change_inf, empty, and size take time O(1), insert, lookup, del, and del_item take time O(log2n) and an intersection operation takes time O(k + log2n), where k is the size of the returned list. Here n is the current size of the set. The space requirement is O(n log n).